{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Family Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Family Tree is also a recursive data structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Added class FamilyTree\n",
      "\n"
     ]
    }
   ],
   "source": [
    "class FamilyTree {\n",
    "    String name;\n",
    "    FamilyTree mother;\n",
    "    FamilyTree father;\n",
    "    \n",
    "    FamilyTree(String name) {\n",
    "        this.name = name;\n",
    "    }\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Added variable me of type FamilyTree with initial value FamilyTree@44e81672\n",
      "\n"
     ]
    }
   ],
   "source": [
    "FamilyTree me = new FamilyTree(\"Doug\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Expression value is: FamilyTree@6aceb1a5\n",
      "|    assigned to temporary variable $3 of type FamilyTree\n",
      "\n",
      "|  Expression value is: FamilyTree@ba4d54\n",
      "|    assigned to temporary variable $4 of type FamilyTree\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "FamilyTree@ba4d54"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "me.mother = new FamilyTree(\"Norma\");\n",
    "me.father = new FamilyTree(\"Scotty\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Doug\n",
      "\n"
     ]
    }
   ],
   "source": [
    "System.out.println(me.name);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Scotty\n",
      "\n"
     ]
    }
   ],
   "source": [
    "System.out.println(me.father.name);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.1 Binary Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The data structure. We'll use this the same way that we did the LinkedList. That is we will have:\n",
    "\n",
    "* Node class - keeps track of next, and data\n",
    "* A BinaryTree class - has all methods, and head\n",
    "\n",
    "For BinaryTrees we will use the terms `left` and `right` instead of `next`, and `root` instead of `head`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "\n",
    "```java\n",
    "class Node {\n",
    "    double data;\n",
    "    Node left;\n",
    "    Node right;\n",
    "    \n",
    "    Node(double data) {\n",
    "        this.data = data;\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```java\n",
    "class BinaryTree {\n",
    "    Node root;\n",
    "    \n",
    "    public void add(Node node) {\n",
    "        if (root == null) {\n",
    "            root = node;\n",
    "        } else {\n",
    "            ///\n",
    "        }\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider adding the method `add(Node)` that would add nodes in no particular order. My natural instincts tell me to let the node do it:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```java\n",
    "class BinaryTree {\n",
    "    Node root;\n",
    "    \n",
    "    public void add(Node node) {\n",
    "        if (root == null) {\n",
    "            root = node;\n",
    "        } else {\n",
    "            root.add(node);\n",
    "        }\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "...and then have Node do it recursively... but..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```java\n",
    "class Node {\n",
    "    double data;\n",
    "    Node left;\n",
    "    Node right;\n",
    "    \n",
    "    Node(double data) {\n",
    "        this.data = data;\n",
    "    }\n",
    "    \n",
    "    public void add(Node node) {\n",
    "        if (left == null)\n",
    "            left = node;\n",
    "        else if (right == null)\n",
    "            right = node;\n",
    "        else {\n",
    "            /// what would go here?\n",
    "        }\n",
    "    }\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "|  Added class Node\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import java.lang.Math;\n",
    "\n",
    "class Node {\n",
    "    double data;\n",
    "    Node left;\n",
    "    Node right;\n",
    "    \n",
    "    Node(double data) {\n",
    "        this.data = data;\n",
    "    }\n",
    "    \n",
    "    public void add(Node node) {\n",
    "        if (left == null)\n",
    "            left = node;\n",
    "        else if (right == null)\n",
    "            right = node;\n",
    "        else {\n",
    "            if (Math.random() < .5) {\n",
    "                left.add(node);\n",
    "            } else {\n",
    "                right.add(node);\n",
    "            }\n",
    "                \n",
    "        }\n",
    "    \n",
    "    }\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Added class BinaryTree\n",
      "\n"
     ]
    }
   ],
   "source": [
    "class BinaryTree {\n",
    "    Node root;\n",
    "    \n",
    "    public void add(Node node) {\n",
    "        if (root == null) {\n",
    "            root = node;\n",
    "        } else {\n",
    "            root.add(node);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Added variable btree of type BinaryTree with initial value BinaryTree@2471cca7\n",
      "\n"
     ]
    }
   ],
   "source": [
    "BinaryTree btree = new BinaryTree();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "btree.add(new Node(23));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "btree.add(new Node(46));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How can we get some feedback about what is in the tree? We could print out the tree, but that is actually a bit difficult. Why?\n",
    "\n",
    "First, let's find the \"depth\" of the tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Replaced class BinaryTree\n",
      "|    Update replaced variable btree, reset to null\n",
      "|    Update overwrote class BinaryTree\n",
      "\n"
     ]
    }
   ],
   "source": [
    "class BinaryTree {\n",
    "    Node root;\n",
    "    \n",
    "    public void add(Node node) {\n",
    "        if (root == null) {\n",
    "            root = node;\n",
    "        } else {\n",
    "            root.add(node);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    public int depth() {\n",
    "        return depth(root);\n",
    "    }\n",
    "    \n",
    "    public int depth(Node node) {\n",
    "        if (node == null) {\n",
    "            return 0;\n",
    "        } else {\n",
    "            return 1 + Math.max(depth(node.left), depth(node.right));\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Modified variable btree of type BinaryTree with initial value BinaryTree@50675690\n",
      "\n"
     ]
    }
   ],
   "source": [
    "BinaryTree btree = new BinaryTree();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Expression value is: 0\n",
      "|    assigned to temporary variable $15 of type int\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "btree.depth()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "btree.add(new Node(23));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Expression value is: 1\n",
      "|    assigned to temporary variable $17 of type int\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "btree.depth()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "btree.add(new Node(46));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Expression value is: 2\n",
      "|    assigned to temporary variable $19 of type int\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "btree.depth()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "|  Expression value is: 2\n",
      "|    assigned to temporary variable $21 of type int\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "btree.add(new Node(47));\n",
    "btree.depth()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "|  Expression value is: 3\n",
      "|    assigned to temporary variable $23 of type int\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "btree.add(new Node(47));\n",
    "btree.depth()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Modified variable btree of type BinaryTree with initial value BinaryTree@5f150435\n",
      "\n"
     ]
    }
   ],
   "source": [
    "BinaryTree btree = new BinaryTree();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "for (int i=0; i < 1000000; i++) {\n",
    "    btree.add(new Node(i));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What do you think the depth is?\n",
    "\n",
    "```java\n",
    "btree.depth();\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Expression value is: 23\n",
      "|    assigned to temporary variable $29 of type int\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "btree.depth();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 3: Sorted Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursive version of add"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Modified class Node\n",
      "|    Update overwrote class Node\n",
      "\n"
     ]
    }
   ],
   "source": [
    "class Node {\n",
    "    double data;\n",
    "    Node left;\n",
    "    Node right;\n",
    "    \n",
    "    Node(double data) {\n",
    "        this.data = data;\n",
    "    }\n",
    "    \n",
    "    public void add(Node node) {\n",
    "        if (node.data < this.data) {\n",
    "            if (this.left == null) {\n",
    "                this.left = node;\n",
    "            } else {\n",
    "                this.left.add(node);\n",
    "            }\n",
    "        } else {\n",
    "            if (this.right == null) {\n",
    "                this.right = node;\n",
    "            } else {\n",
    "                this.right.add(node);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Modified class BinaryTree\n",
      "|    Update overwrote class BinaryTree\n",
      "\n"
     ]
    }
   ],
   "source": [
    "class BinaryTree {\n",
    "    Node root;\n",
    "    \n",
    "    public int depth() {\n",
    "        return depth(root);\n",
    "    }\n",
    "    \n",
    "    public int depth(Node node) {\n",
    "        if (node == null) {\n",
    "            return 0;\n",
    "        } else {\n",
    "            return 1 + Math.max(depth(node.left), depth(node.right));\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    public void add(Node node) {\n",
    "        if (root == null) {\n",
    "            root = node;\n",
    "        } else {\n",
    "            root.add(node);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Modified variable btree of type BinaryTree with initial value BinaryTree@f5f2bb7\n",
      "\n"
     ]
    }
   ],
   "source": [
    "BinaryTree btree = new BinaryTree();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "for (int i=0; i < 1000; i++) {\n",
    "    btree.add(new Node(i));\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Modified variable btree of type BinaryTree with initial value BinaryTree@445b84c0\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "BinaryTree btree = new BinaryTree();\n",
    "for (int i=0; i < 1000000; i++) {\n",
    "    btree.add(new Node(Math.random()));\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|  Expression value is: 50\n",
      "|    assigned to temporary variable $55 of type int\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "50"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "btree.depth()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Non-recursive version of add"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node {\n",
    "    double data;\n",
    "    Node left;\n",
    "    Node right;\n",
    "    \n",
    "    Node(double data) {\n",
    "        this.data = data;\n",
    "    }    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class BinaryTree {\n",
    "    Node root;\n",
    "    \n",
    "    public int depth() {\n",
    "        return depth(root);\n",
    "    }\n",
    "    \n",
    "    public int depth(Node node) {\n",
    "        if (node == null) {\n",
    "            return 0;\n",
    "        } else {\n",
    "            return 1 + Math.max(depth(node.left), depth(node.right));\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    public void add(Node node) {\n",
    "        if (root == null) {\n",
    "            root = node;\n",
    "        } else {\n",
    "            Node current = root;\n",
    "            while (true) {\n",
    "                /// What goes here?\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java 9",
   "language": "java",
   "name": "java9"
  },
  "language_info": {
   "file_extension": ".class",
   "mimetype": "application/java-vm",
   "name": "java"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}